#include <bits/stdc++.h>
#pragma once
using namespace std;



namespace fuh{
    enum Status {EMPTY,EXIST,DELETED};
    template <class Key,class Val>
        struct HashData
        {
            HashData(const pair<Key,Val> &kv = pair<Key,Val>(),Status status=EMPTY)
            :_kv(kv)
            ,_status(status)
            {

            }
            pair<Key,Val> _kv;
            Status _status;
        };
    
    template <class K,class V>
    class HashTable
    {   
        void swap(HashTable& old)
        {
            table.swap(old.table);
            std::swap(_size,old._size);
        }
        size_t hashfunc(const K &key)
        {
            return key%table.size();
        }
        vector<HashData<K,V>> table;
        size_t _size = 0;
        public:
        size_t find(const K &key)
        {
            size_t hashIndex= hashfunc(key);      
            while(table[hashIndex]._status!=Status::EMPTY)//the condition can be found
            {
                if(table[hashIndex]._status==EXIST && table[hashIndex]._kv.first==key)//exist is valid value
                {
                    return hashIndex;
                }
                hashIndex++;
                hashIndex%=table.size();
            }
            return -1;
        }
        bool insert(const pair<K,V> &kv)
        {
            if(find(kv.first)!=-1)//value is existed ,insert fail without insert same value
            {
                return false;
            }
            size_t hashIndex= hashfunc(kv.first);
            if(_size>=table.size()*0.7)//reserve 
            {
                HashTable<K,V> NewHashTb(table.capacity()*2);
                for(int i = 0;i<table.size();i++)
                {
                    if(table[i]._status==EXIST)
                        NewHashTb.insert(table[i]._kv);
                }
                swap(NewHashTb);
            }
            while(table[hashIndex]._status != EMPTY)
            {
                hashIndex++;
                hashIndex %= table.size();
            }
            table[hashIndex]._status = EXIST;
            table[hashIndex]._kv = kv;
            _size++;
            return 1;
        }
        HashTable(size_t size = 10)
        {
            _size = 0;
            table.resize(size);
        }
        bool erase(const K& key)
        {
            int index = find(key);
            if(index!=-1)
            {
                table[index]._status = DELETED;
                _size--;
                return true;
            }
            return false;
        }
        void print()
        {
            for(int i =0;i<table.size();i++)
            {
                cout<<i<<"::->"<<"key::"<<table[i]._kv.first<<"\tstatus::"<<table[i]._status<<endl;
            }
        }
    };


};